package net.projecteuler.prob;

import java.util.List;

import net.projecteuler.util.DigitUtil;
import net.projecteuler.util.PrimeUtil;

public class Problem51 implements Runnable {
	
	private List<Integer> primeList = null;
	private int MAX = 0;
	private boolean[] primeTable = null;
	
	public Problem51(){
		primeList = PrimeUtil.PrimeList;
		MAX = 1000000;
		primeTable = new boolean[MAX];
		for(int i = 0; i < primeList.size(); i++)
			primeTable[primeList.get(i)] = true;
	}

	@Override
	public void run() {
//		int[] family = new int[]{5, 6, 10, 10, 3};
//		System.out.println(getPrimeCnt(family));
		findPrimeFamily(6);
	}
	
	private void findPrimeFamily(int digitCnt){
		int[] digits = new int[digitCnt];
		int attemptReplace = (int) Math.pow(2, digitCnt - 1);
		
		for(int i = 1; i < attemptReplace; i++){
			boolean[] replace = replaceTable(i, digitCnt - 1);
			int fixDigitCnt = 0;
			for(int j = 0; j < replace.length; j++)
				if(!replace[j])
					fixDigitCnt++;
			
			int attemptFixStart = 0;
			if(!replace[replace.length - 1])
				attemptFixStart = (int)Math.pow(10, fixDigitCnt - 1);
			int attemptFix = (int)Math.pow(10, fixDigitCnt);
			
			for(int j = attemptFixStart; j < attemptFix; j++){
				int[] fix = digitTable(j, fixDigitCnt);
				
				int idxFix = 0;
				for(int k = 0; k < replace.length; k++){
					if(replace[k]){
						digits[k + 1] = 10;
					}else{
						digits[k + 1] = fix[idxFix++];
					}
				}
				
				for(int k = 1; k < 10; k += 2){
					digits[0] = k;
					int primeCnt = getPrimeCnt(digits);
					if(primeCnt > 6){
						String str = primeCnt + " :";
						for(int l = 0; l < digits.length; l++)
							str += " " + digits[digits.length - 1 - l];
						System.out.println(str);
					}
				}
			}	
		}
	}
	
	private boolean[] replaceTable(int idx, int length){
		boolean[] result = new boolean[length];
		for(int i = 0; i < length; i++){
			result[i] = idx % 2 == 1;
			idx /= 2;
		}
		return result;
	}
	
	private int[] digitTable(int value, int length){
		int[] result = new int[length];
		for(int i = 0; i < length; i++){
			result[i] = value % 10;
			value /= 10;
		}
		return result;
	}
	
	private int getPrimeCnt(int[] digitFamily){
		int replaceCnt = 0;
		for(int i = 0; i < digitFamily.length; i++)
			if(digitFamily[i] == 10)
				replaceCnt++;
		
		int[] replaceIdx = new int[replaceCnt];
		int idx = 0;
		for(int i = 0; i < digitFamily.length; i++)
			if(digitFamily[i] == 10)
				replaceIdx[idx++] = i;
		
		int primeCnt = 0;
		int[] digitTemp = new int[digitFamily.length];
		for(int i = 0; i < digitFamily.length; i++)
			digitTemp[i] = digitFamily[i];
		
		int startIdx = 0;
		if(digitTemp[digitTemp.length - 1] == 10)
			startIdx = 1;
		
		for(int i = startIdx; i < 10; i++){
			for(int j = 0; j < replaceIdx.length; j++)
				digitTemp[replaceIdx[j]] = i;
			
			if(isPrime(DigitUtil.value(digitTemp)))
				primeCnt++;
		}
		
		return primeCnt;
	}
	
	private boolean isPrime(int value){
		return primeTable[value];
	}
	
	

}
